home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / cc / dist / dbranch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-30  |  13.8 KB  |  450 lines
  1. /* Delayed branch scheduling pass.
  2.    Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is distributed in the hope that it will be useful,
  7. but WITHOUT ANY WARRANTY.  No author or distributor
  8. accepts responsibility to anyone for the consequences of using it
  9. or for whether it serves any particular purpose or works at all,
  10. unless he says so in writing.  Refer to the GNU CC General Public
  11. License for full details.
  12.  
  13. Everyone is granted permission to copy, modify and redistribute
  14. GNU CC, but only under the conditions described in the
  15. GNU CC General Public License.   A copy of this license is
  16. supposed to have been given to you along with GNU CC so you
  17. can know your rights and responsibilities.  It should be in a
  18. file named COPYING.  Among other things, the copyright notice
  19. and this notice must be preserved on all copies.  */
  20.  
  21. /*  Delayed Branch Scheduling Optimization
  22.  
  23. If the HAVE_DELAYED_BRANCH macro is defined in the machine 
  24. description, this code is called by toplev.c during optimizing 
  25. compilation immediately after the final jump optimization pass
  26. and just before assembler output generation, if delayed branch
  27. scheduling is requested with the -fdelayed-branch switch.
  28.  
  29. Machines with delayed branch allow one or more instructions
  30. placed *after* a branch instruction to be executed while the
  31. hardware is off fetching the next instruction.  These instructions
  32. are executed after the branch is issued, but before the branch 
  33. actually takes effect.  The decision as to whether or not
  34. the branch is to be taken, and the address of the branch target
  35. are fixed at the time the branch is issued, so only instructions
  36. that do not appear in the dependency graphs for computing the 
  37. branch decision and/or target address may be relocated "after" 
  38. the branch.  Some machines might have additional restrictions,
  39. such as not allowing memory instructions or condition code
  40. modification in the delay sequence.
  41.  
  42. Note that this scheduling pass occurs after register allocation, and
  43. (of course) final jump optimization.  This mechanism is *not* intended
  44. to be hacked to deal with similar memory-latency pipeline scheduling
  45. (i.e. slots after loads/stores), as tempting as that might be.  The
  46. right place to do load-store latency scheduling is prior to register
  47. allocation, since allocation may introduce artificial dependencies
  48. that could have been avoided; note that these artificial dependencies
  49. are *not* reflected in the flow information, which is one reason for
  50. the somewhat ad hoc analysis done in this pass. 
  51.  
  52. The strategy and methods used are as follows.  The function DBR_SCHEDULE
  53. is called from toplev.c if the scheduling pass is to be run.  That function
  54. sets up the dump file, then scans the current function from top to bottom
  55. for "d-blocks", which are like basic blocks (single-entry, single-exit),
  56. with the additional condition that the last instruction in the block has
  57. delay slots.  Note that if calls have slots, d-blocks can be smaller than
  58. basic blocks.  If a basic block does not end with a delay-instruction,
  59. it is skipped.
  60.  
  61. To re-order instructions in a d-block (see DBR_DBLOCK_SCHED), the scheduler
  62. scans backward from the "d-instruction", trying to fill the slots.  The
  63. scheduler is somewhat conservative.  Volatile memory references are
  64. serialized (their order is never changed to avoid possible aliasing
  65. problems).  Definitions of registers are serialized (so there is no
  66. possibility of deadlock).  Since hard register dependencies are
  67. not noted by flow analysis, the scheduler does its own simplified
  68. tracking of the registers, memory, and condition code uses/defines
  69. by the d-instruction and the instructions it depends on).  Information
  70. available from flow analysis is used to shortcut the analysis where
  71. possible.  
  72.  
  73. Since only data dependencies are considered by the scheduler, any
  74. machine-specific restrictions, e.g. to keep memory instructions from
  75. being scheduled into slots, must be explicit in the definition of
  76. DBR_INSN_ELIGIBLE_P.
  77.  
  78. The scheduler scans backwards over the block, looking for eligible
  79. insns to fill the slot(s).  If none are found, nothing is done, and no
  80. changes are made to the code.  As eligible insns are found, they are
  81. removed from the chain, and recorded in an INSN_LIST rtx.  When all
  82. slots are full (or the top of the d-block is reached), the *pattern*
  83. of the d-insn is replaced with a SEQUENCE rtx, which consists of
  84. a copy of the original d-insn followed by the slot fillers.  Slot
  85. filling instructions remain in the original relative order in the
  86. sequence.
  87.  
  88. When the SEQUENCE pattern is encountered by final, the instructions
  89. are output "normally", though the output code for the instructions
  90. may test for this and alter their behavior appropriately.
  91.  
  92. */
  93.  
  94. #include <stdio.h>
  95. #include "config.h"
  96. #include "rtl.h"
  97. #include "hard-reg-set.h"
  98. #include "flags.h"
  99.  
  100. FILE *dbr_dump_file;
  101.  
  102. /* The number of unfilled delay slots in the current sequence. */
  103. static int slots_avail;
  104.  
  105. /* A flag, nonzero indicating that some insn that could not 
  106.    go in a slot writes to memory.  */
  107.  
  108. static int memw;
  109.  
  110. /* A flag, nonzero indicating that the condition code is written 
  111.    by some insn that couldn't go in a delay slot.  */
  112.  
  113. static int ccw;
  114.  
  115. /* Each bit is nonzero if the corresponding hard register
  116.    is written by an insn that couldn't go in a delay slot.  */
  117.  
  118. static HARD_REG_SET regw;
  119.  
  120. /* A flag, set nonzero if ENOTE determines that
  121.    the current insn can't go in a delay slot because of a
  122.    data dependency detected by note_stores.  */
  123.  
  124. static int eflag;
  125.  
  126. /* The insn having delay slots.  Global because of the calls through
  127.    note_stores that need it.  */
  128.  
  129. static rtx dinsn;
  130.  
  131. /* The insn being currently considered for a delay slot.  */
  132.  
  133. static rtx insn;
  134.  
  135. /* An INSN_LIST (just like the insn field) that we use to hold
  136.    LOG_LINKS of ineligible insns.  We use what flow analysis 
  137.    stuff we can - this prevents exhaustive searches for write-read
  138.    dependencies in most cases.  This tactic only loses on reloads
  139.    and code generated with hard regs (instead of pseudos).  */
  140.  
  141. static rtx dep_insn_list;
  142.  
  143. /* Called by note_stores on "ineligible" insns to keep track of
  144.    pre-branch dependencies.  */
  145. static void
  146. pnote (x, in)
  147.      rtx x;
  148.      rtx in;
  149. {
  150.   switch (GET_CODE (x))
  151.     {
  152.     case REG:
  153.       if (GET_CODE (in) != SET
  154.       || GET_CODE (SET_SRC (in)) != CALL)
  155.     SET_HARD_REG_BIT (regw, REGNO (x));
  156.       return;
  157.     case MEM:
  158.       memw = TRUE; /* this might be relaxed somewhat later */
  159.       return;
  160.     case CC0:
  161.       ccw = TRUE;
  162.       return;
  163.     case PC:
  164.       return;
  165.     default:
  166.       abort (); /* should never happen */
  167.     }
  168. }
  169.  
  170. /*  The d-block end insn is in DINSN.  Initialize the flags to
  171.     start building the delay sequence.  Calls PNOTE from note_stores
  172.     to track the written registers and memory.      */
  173.  
  174. static void
  175. init_flags ()
  176. {
  177.   CLEAR_HARD_REG_SET (regw);
  178.   memw = ccw = 0;
  179.   note_stores (PATTERN (dinsn), pnote);
  180.   if (LOG_LINKS (dinsn))
  181.     dep_insn_list = copy_rtx (LOG_LINKS (dinsn));
  182.   else
  183.     dep_insn_list = 0;
  184.   slots_avail = DBR_SLOTS_AFTER (dinsn);
  185. }
  186.  
  187.  
  188. /* Called through note_stores on possibly eligible insn patterns.
  189.    Checks to see if a register written by the pattern is needed by an already
  190.    ineligible insn.  Sets the global EFLAG nonzero if a dependency
  191.    is found.  */
  192.  
  193. static void 
  194. enote (x, p)
  195.      rtx x;
  196.      rtx p;
  197. {
  198.   if (eflag == 0)
  199.     {
  200.       if (GET_CODE (x) == REG)
  201.     {
  202.       if (reg_used_between_p (x, insn, dinsn))
  203.         goto lose;
  204.       if ((!FUNCTION_VALUE_REGNO_P (REGNO (x)) || 
  205.            GET_CODE (dinsn) != CALL_INSN) &&
  206.           reg_mentioned_p (x, (PATTERN (dinsn))))
  207.         goto lose;
  208.     }
  209.       else if (x == cc0_rtx && 
  210.            reg_used_between_p (x, insn, NEXT_INSN (dinsn)))
  211.     goto lose;
  212.       return;
  213.     lose:
  214.       eflag = 1;
  215.     }
  216. }
  217.  
  218. /*  Search the current dependency list DEP_INSN_LIST for INSN,
  219.     return nonzero if found. */
  220.  
  221. static int
  222. in_dep_list_p (insn)
  223.      rtx insn;
  224. {
  225.   rtx l;
  226.   for (l = dep_insn_list; l ; l = XEXP (l, 1))
  227.     if (insn == XEXP (l, 0)) return 1;
  228.   return 0;
  229. }
  230.  
  231. /* Returns zero if INSN is ineligible to be put in a delay slot
  232.    of DINSN.  INSN is ineligible if it:
  233.      - is in the dependency list of an ineligible insn.
  234.      - writes a hard register needed by an ineligible insn.
  235.      - reads a register written by an ineligible insn.
  236.      - refers to memory.
  237.      - sets the condition code.    
  238.      - violates a machine-dependent constraint.  */
  239.  
  240. static int
  241. insn_eligible_p ()
  242. {
  243.   rtx dest;
  244.   rtx pat = PATTERN (insn);
  245.   int i,s;
  246.  
  247.   /* See if there are any explicit dependencies on this insn. */
  248.   if (in_dep_list_p (insn))
  249.     return 0;
  250.   
  251.   /* Check for implicit dependencies by calling enote on each
  252.      store rtx.  ENOTE makes sure that no ineligible instruction
  253.      refers to a register in a way that flow analysis 
  254.      has missed or ignored.         */
  255.   eflag = 0;
  256.   note_stores (PATTERN (insn), enote);
  257.   if (eflag)
  258.     return 0;
  259.  
  260.   /* Check for volatile memory refs if any already ineligible. */
  261.  
  262.   if (memw && volatile_refs_p (pat))
  263.     {
  264.       memw = TRUE;
  265.       return 0;
  266.     }
  267.  
  268.   /* See if it refers to any regs that are clobbered by ineligibles. */
  269.  
  270.   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  271.     if (TEST_HARD_REG_BIT (regw, i) 
  272.     && refers_to_regno_p (i, i + 1, pat, 0))
  273.       return 0;
  274.  
  275. #ifdef DBR_INSN_ELIGIBLE_P
  276.   /*  Check for arbitrary machine constraints if any. */
  277.   if (! DBR_INSN_ELIGIBLE_P (insn, dinsn))
  278.     return 0;
  279. #endif
  280.  
  281.   return 1;
  282. }
  283.  
  284. /* Add the links in LIST to the dependency list.  We put them
  285.    at the front since this should make searches faster in long
  286.    d-blocks.
  287. */
  288. static void 
  289. prepend_to_dep_list (list)
  290.      rtx list;
  291. {
  292.   rtx l = copy_rtx (list);
  293.   while (XEXP (l, 1) != 0)
  294.     l = XEXP (l, 1);
  295.   XEXP (l, 1) = dep_insn_list;
  296.   dep_insn_list = l;
  297. }
  298.   
  299.  
  300.  
  301. /* Update the flags for ineligible INSN - it can't be put in a delay
  302. slot.  This involves setting bits to indicate the stores of INSN, and
  303. adding any flow-analysis dependencies of INSN's insn-list to
  304. the ineligible list.  (Should ultimately catch reloads too.) */
  305.  
  306. static void 
  307. update_flags (insn)
  308.      rtx insn;
  309. {
  310.   rtx l;
  311.   note_stores (PATTERN (insn), pnote);
  312.   if (l = LOG_LINKS (insn))
  313.     prepend_to_dep_list (l);
  314. }
  315.  
  316. /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
  317.    the pattern of INSN with the SEQUENCE.  Include the available
  318.    slots AVAIL in the SEQUENCE insn.  */
  319. static void
  320. emit_delay_sequence (insn, list, length, avail)
  321.      rtx insn;
  322.      rtx list;
  323.      int length;
  324.      int avail;
  325. {
  326.   register int i = 1;
  327.   register rtx li, tem;
  328.   /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
  329.   rtvec seqv = rtvec_alloc (length + 1);
  330.   rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv);
  331.  
  332.   /* Make a copy of the insn having delay slots. */
  333.   tem = copy_rtx (insn);
  334.   NEXT_INSN (tem) = 0;
  335.   PREV_INSN (tem) = 0;
  336.   /* Replace the original pattern with a sequence whose
  337.      first insn is the copy. */
  338.   PATTERN (insn) = seq;
  339.   INSN_CODE (insn) = -1;
  340.   XVECEXP (seq, 0, 0) = tem;
  341.   /* Copy in the delay-slot filling insns. */
  342.   for (li = list; li; li = XEXP (li, 1))
  343.     {
  344.       XVECEXP (seq, 0, i) = XEXP (li, 0);
  345.       i++;
  346.     }
  347. }
  348.  
  349. /*  Try to reorganize code in a d-block */
  350.  
  351. static void
  352. dbr_dblock_sched (first, last)
  353.      rtx first, last;
  354. { 
  355.   rtx delay_insn_list = 0;
  356.   int seq_len = 0;
  357.   dinsn = last;
  358.   if (first == last) return;
  359.   init_flags ();
  360.   insn = PREV_INSN (dinsn);
  361.   while (1)
  362.     {
  363.       rtx prev = PREV_INSN (insn);
  364.       rtx next = NEXT_INSN (insn);
  365.       if (GET_CODE (insn) == INSN
  366.       && GET_CODE (PATTERN (insn)) != USE
  367.       && GET_CODE (PATTERN (insn)) != CLOBBER
  368.       && GET_CODE (PATTERN (insn)) != ADDR_VEC
  369.       && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
  370.     {
  371.       if (slots_avail >= DBR_INSN_SLOTS (insn) && insn_eligible_p ())
  372.         {
  373.           /* Add this insn to the delay sequence and
  374.          update the number of slots available. */
  375.           register rtx t = delay_insn_list;
  376.           delay_insn_list = gen_rtx (INSN_LIST, VOIDmode, insn, t);
  377.           seq_len++;
  378.           slots_avail -= DBR_INSN_SLOTS (insn);
  379.  
  380.           /* Now remove it from the chain. */
  381.           NEXT_INSN (prev) = next;
  382.           PREV_INSN (next) = prev;
  383.           NEXT_INSN (insn) = PREV_INSN (insn) = 0;
  384.         }
  385.       else
  386.         update_flags (insn);
  387.     }
  388.       else
  389.     if (GET_CODE (insn) != NOTE)
  390.       abort ();
  391.       if (slots_avail == 0 || insn == first)
  392.     break;
  393.       else
  394.     insn = prev;
  395.     }
  396.   /* Done.  If the delay list is non-empty, emit a sequence
  397.      in place of the dinsn.  */
  398.   if (delay_insn_list != 0)
  399.     emit_delay_sequence (dinsn, delay_insn_list, seq_len, slots_avail);
  400. }
  401.  
  402.  
  403. /*
  404. Identify d-blocks of a function, which are sort of like basic
  405. blocks, except that any instruction with delay slots defines the end
  406. of a dblock, and dblocks that do not end in delay-instructions are
  407. uninteresting degenerate cases.
  408.  
  409. This function finds d-blocks in the code for a function, and calls
  410. dbr_dblock_sched on non-degenerate blocks.  Called from toplev.c
  411. if HAVE_DELAYED_BRANCH is defined and we are doing optimizing
  412. compilation.   F is the first insn of the function, DUMP_FILE
  413. is the file to output debugging info on if requested.  */
  414.  
  415. void
  416. dbr_schedule (f, dump_file)
  417.      rtx f;
  418.      FILE *dump_file;
  419. {
  420.   rtx first = f;
  421.   rtx insn;
  422.   /* Dump output if requested */
  423.   if (dbr_dump_file = dump_file)
  424.     fprintf (dbr_dump_file, "Delayed-branch reordering dump.\n");
  425.  
  426.   /* Search for d-blocks by scanning the insns from top to bottom. */
  427.   for (insn = first; insn; insn = NEXT_INSN (insn))
  428.     {
  429.       if (DBR_SLOTS_AFTER (insn) > 0)
  430.     {
  431.       /* An insn with delay slots always terminates a d-block.
  432.          Call the scheduler to fill in the slots if possible. */
  433.       dbr_dblock_sched (first, insn);
  434.       
  435.       /* Resume scanning after the end of the sequence. */
  436.       first = NEXT_INSN (dinsn);
  437.     }
  438.       else
  439.     /* Not an end of a real d-block, but need to check
  440.        if it is the end of a degenerate one.  Note that
  441.        calls or jumps will only reach here if they aren't
  442.        delayed instructions.              */
  443.  
  444.     if (GET_CODE (insn) == CODE_LABEL ||
  445.         GET_CODE (insn) == JUMP_INSN ||
  446.         GET_CODE (insn) == CALL_INSN)
  447.       first = NEXT_INSN (insn);        
  448.     }
  449. }
  450.